package cn.tedu;

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        //定义一个装有字母的二维数组
        char[][] board = {
                {'A', 'B', 'C', 'E'},
                {'S', 'F', 'C', 'S'},
                {'A', 'D', 'E', 'E'}
        };

        String str = "FDECC";
        System.out.println(exist(board, str));
    }

    /**
     * @param board 预设矩阵
     * @param word  要匹配的字符串
     * @return
     */
    public static boolean exist(char[][] board, String word) {
        //获取矩阵宽高
        int h = board.length, w = board[0].length;
        //创建一个相同大小的数组保证坐标与矩阵一一对应并用于记录对应坐标是否已经被使用
        /*
            {
                {false,false,false,false},
                {false,false,false,false},
                {false,false,false,false}
            }
         */
        boolean[][] visited = new boolean[h][w];
        //遍历矩阵,循环调用check方法,找到字符串就返回true,循环结束后仍未找到则返回false
        //第一次循环是循环的board,i最大为board里二维数组的数量(h)
        for (int i = 0; i < h; i++) {
            //第二次循环,循环的是board内里的每一个二维数组
            for (int j = 0; j < w; j++) {
                //每次循环都去检查字符串是否匹配
                boolean flag = check(board, visited, i, j, word, 0);
                System.out.println(i + "-" + j + ":" + flag);
                if (flag) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 递归
     *
     * @param board   原始矩阵
     * @param visited 坐标记录矩阵
     * @param i       循环次数
     * @param j       二次循环次数 (i与j组合即为矩阵中的坐标)
     * @param s       要匹配的字符串
     * @param k       搜索位置(字符串里对应字符的下标)
     * @return
     */
    public static boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
        // 如果当前位置字符与目标字符串对应位置字符不符，直接返回false
        if (board[i][j] != s.charAt(k)) {
            return false;
            // 如果已经匹配到目标字符串的最后一个字符，说明找到了匹配路径，返回true
        } else if (k == s.length() - 1) {
            return true;
        }
        System.out.println(i + "-" + j);
        // 标记当前位置为已访问
        visited[i][j] = true;

        // 定义上、下、左、右四个可能的移动方向(当前坐标需要计算的位移值,不是直接坐标)
        //                      右       左       下       上
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        // 初始化结果为false，用于记录是否在任一方向找到匹配路径
        boolean result = false;

        // 遍历所有可能的方向
        for (int[] dir : directions) {
            //计算位移后的坐标
            int newi = i + dir[0], newj = j + dir[1];

            // 检查新位置是否在矩阵范围内且未访问过
            if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
                // 从新位置开始，匹配下一个字符，如果成功则更新结果并停止循环
                if (!visited[newi][newj]) {
                    boolean flag = check(board, visited, newi, newj, s, k + 1);
                    if (flag) {
                        result = true;
                        break;
                    }
                }
            }
        }

        // 回溯：还原当前位置的访问状态（这一步对后续搜索至关重要）
        visited[i][j] = false;

        // 返回最终搜索结果
        return result;
    }
}